package com.dhu.graph.basic.paths.impls;

import com.dhu.graph.basic.GraphImpls.DiGraph;
import com.dhu.graph.basic.paths.Paths;
import com.dhu.graph.utils.ArrayQueue;

import java.util.Stack;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-03
 * @ Description： 有向图的广度优先搜索，寻找最短有向路径
 * @ Modified By：
 * @ Version:
 */
public class BreadFirstDirectedPaths implements Paths {

    private boolean[] marked;
    private final int s;
    private Integer[] pathsTo;

    public BreadFirstDirectedPaths(DiGraph G, int s){
        this.s = s;
        this.marked = new boolean[G.V()];
        bfs(G, s);
    }
    private void bfs(DiGraph G, int v){
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        queue.enqueue(v);
        while (!queue.isEmpty()) {
            Integer x = queue.dequeue();
            for (Integer w : G.adj(x)) {
                if(!marked[w]){
                    pathsTo[w] = x;
                    queue.enqueue(w);
                }
            }

        }
    }
    @Override
    public Iterable<Integer> pathsTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack<Integer> stack = new Stack<>();
        for (int x = v; v != s; x = pathsTo[x]){
            stack.push(x);
        }
        stack.push(s);
        return stack;
    }

    @Override
    public boolean hasPathTo(Integer v) {
        return marked[v];
    }
}
